1. Field of the Invention
This invention is in the field of synchronous central processors of large-scale, high-performance, general-purpose digital data processing systems. More particularly, this invention relates to method and apparatus for prefetching instructions for a multistaged or central execution pipeline unit (CEPU) of such a central processor.
2. Description of the Prior Art
To increase the performance of the central processors and of the data processing systems of which they are a part, many modifications and improvements have been incorporated into such processors. One such modification is the use of a high-speed cache unit located in the processor to minimize the time required to fetch operands and instructions. To further increase the performance of data processing systems, central processors are synchronized; i.e., a clock produces clock pulses which control each step of the operation of the central processor. Synchronization permits paralleling, overlapping, or pipelining the execution of instructions by dividing the process of executing each instruction into a number of sequential steps, with each instruction going through the same sequence of steps one after another. The result of pipelining is that one instruction will complete its passage through the CEPU at the completion of each clock period, assuming that there are no breaks in the sequence, or in the pipeline. In such central processors, the number of stages, or steps, defined as being the depth of the pipeline.
A pipelined central processor, in order to take maximum advantage of having such capabilities, requires that instructions to be executed, be available, or be prefetched, so that there is no delay caused by the CEPU having to wait for an instruction to be fetched before the pipeline can begin the process of execution of the instruction. Providing the central execution pipeline unit with an instruction prefetch unit is something that is not new to the art; however, there are certain problems with prior art instruction prefetch units. Such prior art instruction prefetch units will fetch instructions only along a given sequential path, or instruction stream. In a given sequential path, or instruction stream, the memory addresses of the instructions of that stream are sequential beginning with the initial instruction of the stream. The addresses of instructions of the stream will be incremented by a given amount, normally one or two, until such time as a branch instruction is encountered. When a branch instruction is encountered, the current instruction stream, or path, is broken, or terminated, and a new instruction stream or path is begun at an address, the target address, specified by the branch instruction.
With prior art prefetch units which can only prefetch instructions along a given instruction stream, at such time as an unconditional branch occurs there is a break in the central execution pipeline unit, and no instructions begin their passage through the steps of the pipeline until the address of the target instruction of the transfer instruction is determined and made available to the CEPU. The magnitude of the delay is a function of the number of steps or stages in the execution pipeline, typically from three to ten clock periods. After such a delay, the target instruction of the branch instruction is fetched and supplied to the central execution unit and operation of the CEPU proceeds until the next branch instruction is executed by the processor.
Another type of instruction which can cause a temporary interruption in the sequential execution of instructions is called an indirect instruction. In executing an indirect instruction, what otherwise would be the address of the operand of the operation to be performed by the instruction, is the address of another word, an indirect word, which indirect word is used in forming the address of the operand or of another indirect word. If the second indirect word contains the address of another word, this word may be either the address of an operand, an address that can be used to form the address of the operand, or the address of another or third indirect word, etc. After prefetching an indirect instruction, it is necessary for the prefetch unit, if it is to avoid breaking the pipeline of the central execution pipeline unit, to fetch the target indirect words and then to prefetch the following sequential instructions of the current instruction stream in which the indirect instruction is located.